package com.hot100.mid;

import java.util.*;

/**
 * @author zhengTao
 * @version 1.0
 * @description:
 * @date 2022/8/7 16:23
 */
public class Demo16 {
    public static void main(String[] args) {
        //String[] nums={"eat","tea","tan","ate","nat","bat"};
        String[] nums={"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"};
        List<List<String>> lists = groupAnagrams(nums);
        System.out.println(lists);
    }

    private static List<List<String>> groupAnagrams(String[] nums) {
        HashMap<String,List<String>> hashMap=new HashMap<>();
        List<List<String>> res=new ArrayList<>();
        for (String num : nums) {
            char[] chars = num.toCharArray();
            Arrays.sort(chars);
            String s = new String(chars);
            if (hashMap.containsKey(s)) {
                List<String> strings = hashMap.get(s);
                strings.add(num);
                hashMap.put(s,strings);
            }else {
                ArrayList<String> strings = new ArrayList<>();
                strings.add(num);
                hashMap.put(s,strings);
            }
        }
        Set<Map.Entry<String, List<String>>> entries = hashMap.entrySet();
        for (Map.Entry<String, List<String>> entry : entries) {
            List<String> value = entry.getValue();
            res.add(value);
        }
        return res;
    }
    //使用质数的方法不行，会溢出
    public static List<List<String>> groupAnagrams1(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        // 字母与质数对应数组
        int[] arr = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101};

        HashMap<Integer, List<String>> map = new HashMap<>();
        int len = strs.length;
        for (int i = 0; i < len; i++) {
            int sum = 1;
            int len2 = strs[i].length();
            // 计算乘积
            for (int j = 0; j < len2; j++) {
                sum *= arr[(strs[i].charAt(j) - 'a')];
            }
            if(map.get(sum) != null) {
                List<String> strList = map.get(sum);
                strList.add(strs[i]);
                map.put(sum, strList);
            }else {
                ArrayList<String> strList = new ArrayList<>();
                strList.add(strs[i]);
                map.put(sum, strList);
            }
        }

        for(Map.Entry<Integer, List<String>> s : map.entrySet()) {
            res.add(s.getValue());
        }

        return res;
    }
}
